package com.LeeCode;

import java.util.HashMap;

/**
 * 分割数组的最多方案数
 */

public class Code2025 {
    public static void main(String[] args) {
        int[] nums = {22, 4, -25, -20, -15, 15, -16, 7, 19, -10, 0, -13, -14};
        int k = -33;
        System.out.println(new Code2025().waysToPartition(nums, k));
    }

    public int waysToPartition(int[] nums, int k) {
        int n = nums.length;
        long[] pre = new long[n];
        pre[0] = nums[0];
        HashMap<Long, Integer> right = new HashMap<>();
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] + nums[i];
            right.merge(pre[i - 1], 1, Integer::sum);
        }
        long total = pre[n - 1];
        int ans = 0;
        if (total % 2 == 0) {
            ans = right.getOrDefault(total / 2, 0);
        }
        HashMap<Long, Integer> left = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int d = k - nums[i];
            if ((total - d) % 2 == 0 && (total + d) % 2 == 0) {
                ans = Math.max(ans, right.getOrDefault((total - d) / 2, 0) +
                        left.getOrDefault((total + d) / 2, 0));
            }
            right.put(pre[i], right.getOrDefault(pre[i], 0) - 1);
            left.merge(pre[i], 1, Integer::sum);
        }
        return ans;
    }
}
